package com.binaryTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ConvertBSTtoGreaterTree0306_538 {

    //迭代法
    public TreeNode convertBST1(TreeNode root) {
        if(root == null) return null;
        int pre = 0;
        Stack<TreeNode> sta = new Stack<>();
        sta.push(root);

        while (!sta.isEmpty()){
            TreeNode node = sta.pop();
            if(node != null) {
                if(node.left !=null) sta.push(node.left);
                sta.push(node);
                sta.push(null);
                if(node.right !=null) sta.push(node.right);
            }else {
                TreeNode temp = sta.pop();
                temp.val += pre;
                pre = temp.val;
            }
        }
        return root;
    }

    //递归
    int sum;
    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        covert(root);
        return root;
    }

    private void covert(TreeNode root) {
        if(root == null) return;

        covert(root.right);

        root.val += sum;
        sum = root.val;

        covert(root.left);
    }
}
